In the modern information age binary values, e.g. ones and zeros, are used to represent and communicate various types of information, e.g. memory, video, audio, statistical information, etc. Unfortunately, during storage, transmission, and/or processing of binary data, errors may be unintentionally introduced (e.g. a ‘1’ bit may be changed to a ‘0’ bit or vice versa).
Several techniques known in the art for overcoming the existence of such errors employ an error correction coding scheme to ensure the reliability of the stored information. The physics of storage methods exhibit a fixed capacity that can be expressed in terms of information bits per storage cell nucleus. This fixed capacity is a direct outcome of the Signal to Noise Ratio (SNR) in each storage nucleus cell, thus defining a theoretical upper limit (known as the “Shannon limit”).
In many cases, such error correction coding scheme require the use of a very long code in order to approach the theoretical correction capability for a given code rate.
However, increasing the code length leads to a complexity and area increase of the encoder and decoder circuitry. The result is that at some point it is no longer practical or efficient to implement an integrated circuit comprising such error correction coding scheme. Alternatively, there exists insufficient silicon density to support standard decoding techniques.
The term “error correction” (i.e. the detection and correction of errors) is applied herein to data storage. Encoding and decoding, according to forward error-correcting codes, are carried out either in software or with hardware.
Once the Shannon limit [1] was discovered, there was a need to provide codes that come close to the performance limits of Shannon's information theorem. It is well known [2]-[5] that in order to approach these limits one must increase the code length. In 1993, Berron [6] was the first to present near capacity approaching techniques using iterative decoding. However, only long codes were considered. Later on [7]-[11] with the introduction of Low Density Parity Check (LDPC) codes, new structures that came even closer to these capacity limits were successfully presented, again only for long codes, typically about 107 bits long.
Specific schemes based on LDPC iterative decoders are depicted in [12]-[14], where a high emphasis is made to reduce the implementation complexity of the computation units, the number of iterations, the required memory size, etc.
In order to implement these long codes in a complexity restricted environment and benefit from their performance, there is thus a need for providing a method to reduce the circuitry complexity of the encoder and decoder of long codes such that practical shorter schemes could be employed.
A prior art technique disclosing a puncturing method for reducing the circuitry complexity of the encoder and decoder by reducing the parity overhead is taught by US Patent Application No. 20050160350 to Dror et al.
The Dror patent discloses a high-speed data encoder/decoder providing a single-bit forward error-correction. The data is arranged to be protected within a rectangular array, such that the location of a single bit error is determined according to row and column positions. As a result, the size of lookup tables provided for converting error syndromes to error locations is reduced.
However, each of the two computation phases disclosed in the Dror patent is not by itself an error correction scheme as it does not provide enough information for correcting a single error in the first phase. Therefore, the first phase cannot correct even a single error in each sub-code without depending on computations obtained at the second phase.